package leetCode.hw.dp;

/**
 *  * 背包问题：
 *  *
 *  * 问题描述：有一个背包可以装物品的总重量为W，现有N个物品，每个物品重w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？
 *  *
 *  * 背包问题解题方法：
 *  * 定义dp[i][j], 表示前i个物品，背包重量为j的情况下能装的最大价值
 *
 *  * 例如： dp[3][4] = 6表示用前3个物品装入重量为4的背包所能获得的最大价值为6，
 *  * 这时并不是三个物品全部装入,而是三个物品满足装入背包的条件下的最大价值
 *  *
 *  * 状态转移方程为：
 *  * dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
 *  *
 *  * dp[i-1][j]表示当前物品不放入背包
 *  * dp[i-1][j-w[i]]+v[i] 表示当前物品放入背包
 *  * 即当前第i个物品要么放入背包，要么不放入背包
 */
public class HJ16_1Solution implements HJ16_1 {

    /**
     * 背包问题动态规划
     * @param weight
     * @param price
     * @param maxWeight
     * @return
     */
    @Override
    public int getMaxPrice(int[] weight, int[] price,int maxWeight) {
        int m = weight.length;
        int[][] dp = new int[m+1][maxWeight+1];
        //dp[0][x] dp[x][0] 都默认为0
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=maxWeight;j++) {
                // 当前物品放入背包
                if(j-weight[i-1]>=0) {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+price[i-1]);
                }
                // 当前物品不放入背包
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[m][maxWeight];
    }

    public static void main(String[] args) {
        int[] weight = {4,6,7,8};
        int[] price = {50,60,100,70};
        System.out.println(new HJ16_1Solution().getMaxPrice(weight,price,15));
    }


}
